2007-11-30 Fri., Math 319

Math 319
Finish up IP, start NLP

just discuss these, don't bother to formulate them:
Bin-Packing Problem
Warehouse-Dealership Problem
[ didn't get to set-covering, etc.]
Set-Covering/Partitioning/Packing
   set covering: some overlap allowed (e.g. ambulance zones in a city), no empty space
      usually minimize-cost
   set partitioning: [skip description until after Packing]: no overlap, no empty space
      could be min-cost or max-profit
   set packing: literally packing items in a box, no overlap but some empty space allowed
      usually maximize-profit of items put in.

[notes for self:]
NLP learning objectives:
   natur of convex vs. concave solutions
   local vs. global optimality
   relative difficulty vs. LP & IP
   solutions: setepest descent, Newton's, line search, etc.
   want smooth func w/ easy deriv.
   can't just force x*(1-x)=0 for binary vars

[notes for self:]
Example NLPs
   L2 regression
   L2 facility location
   Mfg. allocation (economies of scale)
   electric power alloc (diseconomies of scale)
   protein folding/drug discovery
   hanging chain
   Markowitz portfolios
   user vs. social optimum
   shotspotter
   sinusoid or exponential regression

NLP: Chapter 12
   will come back to Chs 10 & 11 (skipping 8 & 9)
   Bad chapter titles: Ch 7 "Discrete Optimization" even though LP is continuous
   usually, Discrete optimization = IP

Manufacturing Allocation (economies of scale)
   we manufacture cars at 2 plants
      Plant 1: total cost to produce x cars is sqrt(x) thousand $
      Plant 2: total cost to produce x cars is 0.5*sqrt(x) + 20 thousand $
   Combined production at least 2500
   Ask class to formulate & solve it themselves
      e.g. min sqrt(x) + 0.5*sqrt(y) + 20
   s.t. x + y >= 2500, x&y >= 0

     setting up in Excel: should have cells for coefficients like a*sqrt(x)+b

	once students get the Solver solution, try changing the 0.5 until soln jumps.

   graph feas. region, check corner points
      0,2500: 0.5*50+20 = 45
      2500,0: 50 + 20 = 70
(didn't do computer contour plots:)
   SciLab contour plot (have it avail. on the screen)
deff('z=cars(x,y)','z=sqrt(x) + 0.5*sqrt(y) + 20'); contour2d(0:50:3000,0:50:3000,cars,45:5:80)
plot([0,2500],[2500,0],'-k') 
	Or do a surface plot in Excel.
   other points on the line in between?
      900,1600: 30+0.5*40+20 = 70
      1600,900: 40+0.5*30+20 = 75
      625,0: 25+0+20=45 (other end of contour through optimal point)

Diseconomies of Scale: Electric Power
   Generator 1: to produce x GW, total cost = 3*x^2 for x in 0 to 5
   Generator 2: to produce y GW, total cost = 2*y^2
   need total production >= 4 GW
   students should formulate & solve in Excel as before.
   try cornerpoints:
      0,4: $32
      4,0: $48
   also:
      2,2:  $20
      1,3: $3+18=21
      3,1: $29
(didn't do computer contour plots:)
deff('z=elec(x,y)','z=3*x2+2*y2'); contour2d(0:.1:5,0:.1:5,elec,18:1:50)
plot([0,4],[4,0],'-k')     True optimum? (d/dx) 3x2+2*(4-x)2 = 6x+4*(4-x)*-1=10x-16
      set =0, x=1.6 y=2.4 cost=$19.2
   not at a corner point!

What's the difference?
   feas. region had same shape.
   mfg: cost function concave-down
   elec: cost function concave-up
in NLP, a lot depends on the shape of the feas. region & obj.func.
-------------------- got here --------------
   min concave-down over convex region -> optimum @ corner points, soln. is jumpy
   min concave-up over convex region -> optimum @ anywhere, usually changes smoothly

L2 facility location
l2 linear regression